<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta property="og:type" content="website">
<meta property="og:title" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:url" content="http://example.com/page/7/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="StarsWhisper">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main">
  
    <article id="post-【线段树练习】 洛谷线段树模板1 CF1288E" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90%E7%BA%BF%E6%AE%B5%E6%A0%91%E7%BB%83%E4%B9%A0%E3%80%91%20%E6%B4%9B%E8%B0%B7%E7%BA%BF%E6%AE%B5%E6%A0%91%E6%A8%A1%E6%9D%BF1%20CF1288E/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90%E7%BA%BF%E6%AE%B5%E6%A0%91%E7%BB%83%E4%B9%A0%E3%80%91%20%E6%B4%9B%E8%B0%B7%E7%BA%BF%E6%AE%B5%E6%A0%91%E6%A8%A1%E6%9D%BF1%20CF1288E/">【线段树练习】 洛谷线段树模板1 CF1288E.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E6%80%9D%E6%83%B3or%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">思想or数据结构</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="洛谷-p3372-线段树模板1"><a class="markdownIt-Anchor" href="#洛谷-p3372-线段树模板1"></a> 洛谷 P3372 线段树模板1</h2>
<p>​<br />
#include &lt;bits/stdc++.h&gt;</p>
<pre><code>const int N = 1e5+4;
typedef long long LL;
LL val[N&lt;&lt;2],lazy[N&lt;&lt;2];
int qu[N];
int n,m,x,y,k,op;

int getMid(int l,int r)
&#123;
   return (l+r) &gt;&gt; 1;
&#125;

void build(int l,int r,int rt)
&#123;
   if(l == r) val[rt] = qu[r];
   else&#123;
      int mid = getMid(l,r);
      build(l,mid,rt&lt;&lt;1);
      build(mid+1,r,rt&lt;&lt;1|1);
      val[rt] = val[rt&lt;&lt;1] + val[rt&lt;&lt;1|1];
   &#125;
&#125;

void pushdown(int l,int r,int rt)
&#123;
   if(!lazy[rt]) return;
   int mid = getMid(l,r);
   lazy[rt&lt;&lt;1] += lazy[rt];
   lazy[rt&lt;&lt;1|1] += lazy[rt];
   val[rt&lt;&lt;1] += lazy[rt]*(mid-l+1);
   val[rt&lt;&lt;1|1] += lazy[rt]*(r-mid);
   lazy[rt] = 0;
&#125;
</code></pre>
<p>​<br />
LL query(int sl,int sr,int l,int r,int rt)<br />
{<br />
if(sl &gt;= l &amp;&amp; sr &lt;= r) return val[rt];<br />
pushdown(sl,sr,rt);<br />
int mid = getMid(sl,sr);<br />
if(r &lt;=mid) return query(sl,mid,l,r,rt&lt;&lt;1);<br />
else if(l &gt; mid) return query(mid+1,sr,l,r,rt&lt;&lt;1|1);<br />
else return query(sl,mid,l,r,rt&lt;&lt;1) + query(mid+1,sr,l,r,rt&lt;&lt;1|1);<br />
}</p>
<pre><code>void update(int sl,int sr,int l,int r,int v,int rt)
&#123;
   if(sl &gt;= l &amp;&amp; sr &lt;= r)&#123;
      val[rt] += v*(sr-sl+1);
      lazy[rt] += v;
      return ;
   &#125;
   pushdown(sl,sr,rt);
   int mid = getMid(sl,sr);
   if(r &lt;= mid) update(sl,mid,l,r,v,rt&lt;&lt;1);
   else if(l &gt; mid)  update(mid+1,sr,l,r,v,rt&lt;&lt;1|1);
   else&#123;
      update(sl,mid,l,r,v,rt&lt;&lt;1);
      update(mid+1,sr,l,r,v,rt&lt;&lt;1|1);
   &#125;
   val[rt] = val[rt&lt;&lt;1] + val[rt&lt;&lt;1|1];
&#125;

void show(int l,int r,int rt)
&#123;
   if(l == r) &#123;printf(&quot;%lld &quot;,val[rt]); return ;&#125;
   pushdown(l,r,rt);
   int mid = getMid(l,r);
   show(l,mid,rt&lt;&lt;1);
   show(mid+1,r,rt&lt;&lt;1|1);
&#125;

int main()
&#123;
   scanf(&quot;%d%d&quot;,&amp;n,&amp;m);
   for(int i=0; i&lt;n; i++)&#123;
      scanf(&quot;%d&quot;,&amp;qu[i]);
   &#125;
   build(0,n-1,1);
   for(int i=0; i&lt;m; i++)&#123;
      scanf(&quot;%d&quot;,&amp;op);
      if(op == 2)&#123;
         scanf(&quot;%d%d&quot;,&amp;x,&amp;y);
         printf(&quot;%lld\n&quot;,query(0,n-1,x-1,y-1,1));
      &#125;
      else&#123;
         scanf(&quot;%d%d%d&quot;,&amp;x,&amp;y,&amp;k);
         update(0,n-1,x-1,y-1,k,1);
      &#125;
      //show(0,n-1,1);
      //std::cout &lt;&lt; std::endl;
   &#125;

   return 0;
&#125;
</code></pre>
<p>​</p>
<h2 id="cf1288e"><a class="markdownIt-Anchor" href="#cf1288e"></a> CF1288E</h2>
<p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/CF1288E">https://www.luogu.com.cn/problem/CF1288E</a><br />
<strong>最小的排名</strong> 可想而知，若发过消息，则是1，否则为初始值。<br />
<strong>最大的排名</strong> ，用线段树记录：</p>
<blockquote>
<p>假设人数为N，发消息次数为M，则开一个区间大小为M+N的线段树，用于记录所有人的最大排名。前M位初始化为1，后N为为[1，2，3，4…N]。（代码中用qu[]数组模拟出这样的值，然后初始化线段树），初始化整形变量idx=M</p>
</blockquote>
<p>把每个人的最小排名和最晚排名都初始化为其序号。</p>
<p>用qu[]数组记录每个人最后出现的位置。(发一次消息算出现一次，qu[]具体表示什么，看完下方的3条就明白了)</p>
<h4 id="每当一个人i发消息"><a class="markdownIt-Anchor" href="#每当一个人i发消息"></a> 每当一个人i发消息：</h4>
<p>1.更新这个人的最小排名为1，最大排名为max(原最大排名,线段树查询qu[i]位置的结果)<br />
2.把区间[idx+1,qu[i]]即这个人以及之前所有人对应的区间+1（是否包含这个人时无所谓的）<br />
3.然后把这个人提前为第一个人，即qu[i]改为出现的位置改为idx–（也可以先提前，这样的话线段树区间应该初始化为0），</p>
<h4 id="输出答案时"><a class="markdownIt-Anchor" href="#输出答案时"></a> 输出答案时</h4>
<p>最小排名即记录中的最小排名，直接输出<br />
最大排名为max(记录中的最大排名，线段树查询qu[i]位置的结果)</p>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <cstdlib><br />
#include <algorithm><br />
#include <vector><br />
#include <map><br />
#include <string><br />
typedef long long int LL;<br />
typedef std::pair&lt;int ,int&gt; PP;<br />
const int N = 3e5+2;<br />
int lazy[(N+N)&lt;&lt;2];<br />
PP span[N];<br />
int qu[N+N];<br />
int idx;<br />
int n,m,k;<br />
void build(int l,int r,int rt)<br />
{<br />
if(l == r){<br />
lazy[rt] = qu[l];<br />
return ;<br />
}<br />
int mid = (l+r) &gt;&gt; 1;<br />
build(l,mid,rt&lt;&lt;1);<br />
build(mid+1,r,rt&lt;&lt;1|1);<br />
}</p>
<pre><code>void pushdown(int rt)
&#123;
   if(!lazy[rt]) return;
   lazy[rt&lt;&lt;1] += lazy[rt];
   lazy[rt&lt;&lt;1|1] += lazy[rt];
   lazy[rt] = 0;
&#125;

void update(int sl,int sr,int l,int r,int val,int rt)
&#123;
   if(sl &gt;=l &amp;&amp; sr&lt;=r) &#123;
      lazy[rt] += val;
      return ;
   &#125;
   pushdown(rt);
   int mid = (sl+sr) &gt;&gt; 1;
   if(l&lt;=mid) update(sl,mid,l,r,val,rt&lt;&lt;1);
   if(r&gt;mid) update(mid+1,sr,l,r,val,rt&lt;&lt;1|1);
&#125;

int query(int sl,int sr,int l,int r,int rt)
&#123;
   if(sl&gt;=l &amp;&amp; sr&lt;=r)&#123;
      return lazy[rt];
   &#125;
   pushdown(rt);
   int mid = (sl+sr) &gt;&gt; 1;
   if(l&lt;=mid)  return query(sl,mid,l,r,rt&lt;&lt;1);
   else   return query(mid+1,sr,l,r,rt&lt;&lt;1|1);
&#125;

int main()
&#123;
   scanf(&quot;%d%d&quot;,&amp;n,&amp;m);
   idx = m;
   for(int i=1; i&lt;=n; i++)&#123;
      span[i].second = span[i].first = i;
      qu[i+m] = i;
   &#125;
   for(int i=1; i&lt;=m; i++)&#123;
      qu[i] = 1;
   &#125;
   build(1,n+m,1);
   for(int i=1; i&lt;=n; i++)&#123;
      qu[i] = i+m;
   &#125;
   for(int i=0; i&lt;m; i++)&#123;
      scanf(&quot;%d&quot;,&amp;k);
      span[k].second = std::max(span[k].second,query(1,n+m,qu[k],qu[k],1));
      span[k].first = 1;
      update(1,n+m,idx+1,qu[k],1,1);

      qu[k] = idx--;

   &#125;
   for(int i=1; i&lt;=n; i++)&#123;
      span[i].second = std::max(span[i].second,query(1,n+m,qu[i],qu[i],1));
      printf(&quot;%d %d\n&quot;,span[i].first,span[i].second);
   &#125;
   return 0;
&#125;
</code></pre>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90%E7%BA%BF%E6%AE%B5%E6%A0%91%E7%BB%83%E4%B9%A0%E3%80%91%20%E6%B4%9B%E8%B0%B7%E7%BA%BF%E6%AE%B5%E6%A0%91%E6%A8%A1%E6%9D%BF1%20CF1288E/" data-id="cl2uhoeda004ge4j35qj13x09" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%BA%BF%E6%AE%B5%E6%A0%91/" rel="tag">线段树</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【线段树】  L3-017 森森快递 (30分)  27分WA代码" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90%E7%BA%BF%E6%AE%B5%E6%A0%91%E3%80%91%20%20L3-017%20%E6%A3%AE%E6%A3%AE%E5%BF%AB%E9%80%92%20(30%E5%88%86)%20%2027%E5%88%86WA%E4%BB%A3%E7%A0%81/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90%E7%BA%BF%E6%AE%B5%E6%A0%91%E3%80%91%20%20L3-017%20%E6%A3%AE%E6%A3%AE%E5%BF%AB%E9%80%92%20(30%E5%88%86)%20%2027%E5%88%86WA%E4%BB%A3%E7%A0%81/">【线段树】  L3-017 森森快递 (30分)  27分WA代码.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E6%80%9D%E6%83%B3or%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">思想or数据结构</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="l3-017-森森快递-30分"><a class="markdownIt-Anchor" href="#l3-017-森森快递-30分"></a> L3-017 森森快递 (30分)</h2>
<p>森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的N个城市，这些城市从左到右依次从0到(N−1)编号。由于道路限制，第i号城市（i=0,⋯,N−2）与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过C<br />
​i<br />
​​ 公斤。</p>
<p>公司开张后很快接到了Q张订单，其中j张订单描述了某些指定的货物要从S<br />
​j<br />
​​ 号城市运输到T<br />
​j<br />
​​ 号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。</p>
<p>为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输，则这两张订单的运输同时受2-3以及3-4两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。</p>
<h2 id="输入格式"><a class="markdownIt-Anchor" href="#输入格式"></a> 输入格式：</h2>
<p>输入在第一行给出两个正整数N和Q（2≤N≤10<br />
​5<br />
​​ , 1≤Q≤10<br />
​5<br />
​​ ），表示总共的城市数以及订单数量。</p>
<p>第二行给出(N−1)个数，顺次表示相邻两城市间的道路允许的最大运货重量C<br />
​i<br />
​​ （i=0,⋯,N−2）。题目保证每个C<br />
​i<br />
​​ 是不超过2<br />
​31<br />
​​ 的非负整数。</p>
<p>接下来Q行，每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法，并且不存在起点和终点重合的情况。</p>
<h2 id="输出格式"><a class="markdownIt-Anchor" href="#输出格式"></a> 输出格式：</h2>
<p>在一行中输出可运输货物的最大重量。</p>
<h2 id="输入样例"><a class="markdownIt-Anchor" href="#输入样例"></a> 输入样例：</h2>
<p>10 6<br />
0 7 8 5 2 3 1 9 10<br />
0 9<br />
1 8<br />
2 7<br />
6 3<br />
4 5<br />
4 2</p>
<h2 id="输出样例"><a class="markdownIt-Anchor" href="#输出样例"></a> 输出样例：</h2>
<p>7</p>
<h2 id="样例提示"><a class="markdownIt-Anchor" href="#样例提示"></a> 样例提示：</h2>
<p>我们选择执行最后两张订单，即把5公斤货从城市4运到城市2，并且把2公斤货从城市4运到城市5，就可以得到最大运输量7公斤。</p>
<p>​<br />
#include <iostream><br />
#include <cstdio><br />
#include <cstring><br />
#include <algorithm></p>
<pre><code>const int maxn=1e5+5;

int n,q;
int vv1,vv2;
int ans;

struct Node
&#123;
    int val,lz;
&#125;tree[maxn&lt;&lt;2];
</code></pre>
<p>​<br />
int getMid(int a,int b){ return (a+b)&gt;&gt;1; }</p>
<p>​<br />
​<br />
void build(int l,int r,int rt)<br />
{<br />
tree[rt].lz=0;<br />
if(l==r)<br />
{<br />
std::cin &gt;&gt; tree[rt].val;<br />
return ;<br />
}<br />
else<br />
{<br />
int mid=getMid(l,r);<br />
build(l,mid,rt&lt;&lt;1);<br />
build(mid+1,r,rt&lt;&lt;1|1);<br />
}<br />
tree[rt].val=std::min(tree[rt&lt;&lt;1].val,tree[rt&lt;&lt;1|1].val);<br />
}</p>
<pre><code>void pushDown(int rt)
&#123;
    if(!tree[rt].lz) return ;
    tree[rt&lt;&lt;1].val-=tree[rt].lz;
    tree[rt&lt;&lt;1|1].val-=tree[rt].lz;
    tree[rt&lt;&lt;1].lz+=tree[rt].lz;
    tree[rt&lt;&lt;1|1].lz+=tree[rt].lz;
    tree[rt].lz=0;
&#125;

void update(int sl,int sr,int l,int r,int rt,int val)
&#123;
    if(l&gt;=sl &amp;&amp; r&lt;=sr)
    &#123;
        tree[rt].val-=val;
        tree[rt].lz+=val;
        return ;
    &#125;
    pushDown(rt);
    int mid=getMid(l,r);
    if(sr&lt;=mid) update(sl,sr,l,mid,rt&lt;&lt;1,val);
    else if(sl&gt;mid) update(sl,sr,mid+1,r,rt&lt;&lt;1|1,val);
    else
    &#123;
        update(sl,sr,l,mid,rt&lt;&lt;1,val);
        update(sl,sr,mid+1,r,rt&lt;&lt;1|1,val);
    &#125;
//子树update完之后，根还还还还还还还还要取子树最小值
    tree[rt].val=std::min(tree[rt&lt;&lt;1].val,tree[rt&lt;&lt;1|1].val);
&#125;

int query(int sl,int sr,int l,int r,int rt)
&#123;
    if(l&gt;=sl &amp;&amp; r&lt;=sr) return tree[rt].val;
    pushDown(rt);
    int mn=2147483647,mid=getMid(l,r);
    if(sr&lt;=mid) mn=std::min(mn,query(sl,sr,l,mid,rt&lt;&lt;1));
    else if(sl&gt;mid) mn=std::min(mn,query(sl,sr,mid+1,r,rt&lt;&lt;1|1));
    else
    &#123;
        mn=std::min(mn,query(sl,sr,l,mid,rt&lt;&lt;1));
        mn=std::min(mn,query(sl,sr,mid+1,r,rt&lt;&lt;1|1));
    &#125;
    return mn;
&#125;

bool cmp(std::pair&lt;int ,int &gt; a,std::pair&lt;int ,int &gt; b)
&#123;
    if(a.second-a.first==b.second-b.first) return a.first&lt;b.first;
    return a.second-a.first&lt;b.second-b.first;
&#125;

int main()
&#123;
    std::cin &gt;&gt; n &gt;&gt; q;
    std::pair&lt;int ,int &gt; pa[q];
    build(1,n-1,1);
    ans=0;
    for(int i=0; i&lt;q; i++)
    &#123;
        std::cin &gt;&gt; pa[i].first &gt;&gt; pa[i].second;
        if(pa[i].first&gt;pa[i].second) std::swap(pa[i].first,pa[i].second);
//线段树的一个点表示相邻的一段路，所以要second-1
//但由于题目的城市编号从0开始，这里默认从1开始，所以变成first+1
        pa[i].first+=1;
    &#125;
    std::sort(pa,pa+q,cmp);
    for(int i=0; i&lt;q; i++)
    &#123;
        int ch=query(pa[i].first,pa[i].second,1,n-1,1);
        ans+=ch;
        update(pa[i].first,pa[i].second,1,n-1,1,ch);
    &#125;
    std::cout &lt;&lt; ans;

    return 0;
&#125;
</code></pre>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90%E7%BA%BF%E6%AE%B5%E6%A0%91%E3%80%91%20%20L3-017%20%E6%A3%AE%E6%A3%AE%E5%BF%AB%E9%80%92%20(30%E5%88%86)%20%2027%E5%88%86WA%E4%BB%A3%E7%A0%81/" data-id="cl2uhoedb004ke4j3gh3hgjpo" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%BA%BF%E6%AE%B5%E6%A0%91/" rel="tag">线段树</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【背包DP练习】洛谷 P5020货币系统 P1757通天之分组背包 P1064[NOIP2006 提高组]金明的预算方案 P5322 [BJOI2019]排兵布阵" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90%E8%83%8C%E5%8C%85DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P5020%E8%B4%A7%E5%B8%81%E7%B3%BB%E7%BB%9F%20P1757%E9%80%9A%E5%A4%A9%E4%B9%8B%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85%20P1064%5BNOIP2006%20%E6%8F%90%E9%AB%98%E7%BB%84%5D%E9%87%91%E6%98%8E%E7%9A%84%E9%A2%84%E7%AE%97%E6%96%B9%E6%A1%88%20P5322%20%5BBJOI2019%5D%E6%8E%92%E5%85%B5%E5%B8%83%E9%98%B5/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90%E8%83%8C%E5%8C%85DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P5020%E8%B4%A7%E5%B8%81%E7%B3%BB%E7%BB%9F%20P1757%E9%80%9A%E5%A4%A9%E4%B9%8B%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85%20P1064%5BNOIP2006%20%E6%8F%90%E9%AB%98%E7%BB%84%5D%E9%87%91%E6%98%8E%E7%9A%84%E9%A2%84%E7%AE%97%E6%96%B9%E6%A1%88%20P5322%20%5BBJOI2019%5D%E6%8E%92%E5%85%B5%E5%B8%83%E9%98%B5/">【背包DP练习】洛谷 P5020货币系统 P1757通天之分组背包 P1064[NOIP2006 提高组]金明的预算方案 P5322 [BJOI2019]排兵布阵.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/DP/">DP</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="洛谷-p5020货币系统"><a class="markdownIt-Anchor" href="#洛谷-p5020货币系统"></a> 洛谷 P5020货币系统</h2>
<p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P5020">https://www.luogu.com.cn/problem/P5020</a></p>
<p>思路是把货币从小到大排序，然后按顺序依次完全背包dp，每次dp检查i-1种面值的货币能不能凑出第i种货币<br />
<s>做完看了看，这个思路始终进行着令人尴尬的重复，但是懒得改了</s><br />
<s>然后去题解看了看发现没有比这还麻烦的方法</s><br />
.<br />
最后四个样例数据范围比较大，但应该都不是需要时间特别长的，而是卡一些技巧。<br />
80分代码：修改一（不是亿）点点就可以满分</p>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <algorithm><br />
#include <cmath><br />
#include <cstdlib><br />
#include <queue><br />
#include <map><br />
#include <set><br />
#include <stack><br />
#include <vector><br />
typedef long long LL;<br />
typedef std::pair&lt;int ,int&gt; PP;<br />
const int N = 25005,M = 105;<br />
int dp[N],val[M],kik[M];<br />
int n,m,t,cnt;<br />
int main()<br />
{<br />
scanf(&quot;%d&quot;,&amp;t);<br />
while(t–){<br />
memset(dp,0,sizeof(dp));<br />
memset(kik,0,sizeof(kik));<br />
scanf(&quot;%d&quot;,&amp;n);<br />
for(int i=0; i&lt;n; i++){<br />
scanf(&quot;%d&quot;,&amp;val[i]);<br />
}<br />
std::sort(val,val+n);<br />
for(int i=1; i&lt;n; i++){<br />
for(int j=0; j&lt;i; j++){<br />
if(kik[j]) continue;<br />
for(int k=val[j]; k&lt;=val[i]; k++){<br />
dp[k] = std::max(dp[k],dp[k-val[j]]+val[j]);<br />
}<br />
}<br />
if(dp[val[i]] == val[i]) kik[i] = 1;<br />
}<br />
cnt = 0;<br />
for(int i=0; i&lt;n; i++){<br />
if(!kik[i]){<br />
cnt += 1;<br />
}<br />
}<br />
printf(&quot;%d\n&quot;,cnt);<br />
}<br />
return 0;<br />
}</p>
<p>TEL原因是 仅仅在for i 的一层循环中检查是否剔除面值i，做了很多无用功。<br />
修改：<br />
在for j的一层循环中，若出现面值i已经被凑出来，则不用把循环全部进行完，退出循环即可。这样可以节省一些时间<br />
做出该修改后得分95，还是未AC<br />
于是又在每次dp面值i之前先检查之前是否出现过可以被面值i整除的面值，有的话直接剔除，终于AC<br />
AC代码：</p>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <algorithm><br />
#include <cmath><br />
#include <cstdlib><br />
#include <queue><br />
#include <map><br />
#include <set><br />
#include <stack><br />
#include <vector><br />
typedef long long LL;<br />
typedef std::pair&lt;int ,int&gt; PP;<br />
const int N = 25005,M = 105;<br />
int dp[N],val[M],kik[M];<br />
int n,m,t,cnt;<br />
int main()<br />
{<br />
scanf(&quot;%d&quot;,&amp;t);<br />
while(t–){<br />
memset(dp,0,sizeof(dp));<br />
memset(kik,0,sizeof(kik));<br />
scanf(&quot;%d&quot;,&amp;n);<br />
for(int i=0; i&lt;n; i++){<br />
scanf(&quot;%d&quot;,&amp;val[i]);<br />
}<br />
std::sort(val,val+n);<br />
for(int i=1; i&lt;n; i++){<br />
for(int j=0; j&lt;i; j++){<br />
if(val[i]%val[j] == 0){<br />
kik[i] = 1;<br />
break;<br />
}<br />
}<br />
if(kik[i]) continue;<br />
for(int j=0; j&lt;i; j++){<br />
if(kik[j]) continue;<br />
for(int k=val[j]; k&lt;=val[i]; k++){<br />
dp[k] = std::max(dp[k],dp[k-val[j]]+val[j]);<br />
}<br />
if(dp[val[i]] == val[i]) break;<br />
}<br />
if(dp[val[i]] == val[i]) kik[i] = 1;<br />
}<br />
cnt = 0;<br />
for(int i=0; i&lt;n; i++){<br />
if(!kik[i]){<br />
cnt += 1;<br />
}<br />
}<br />
printf(&quot;%d\n&quot;,cnt);<br />
}<br />
return 0;<br />
}</p>
<h2 id="洛谷-p1757-通天之分组背包"><a class="markdownIt-Anchor" href="#洛谷-p1757-通天之分组背包"></a> 洛谷 P1757 通天之分组背包</h2>
<p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1757">https://www.luogu.com.cn/problem/P1757</a><br />
分组背包</p>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <algorithm><br />
#include <cmath><br />
#include <cstdlib><br />
#include <queue><br />
#include <map><br />
#include <set><br />
#include <stack><br />
#include <vector><br />
typedef long long LL;<br />
typedef std::pair&lt;int ,int&gt; PP;<br />
const int N = 1005,M = 105;</p>
<pre><code>int m,n,w,v,g,gg;
struct Item
&#123;
   int value,weight;
&#125;gr[N][N];
int num[N],mp[N];
int dp[N];
int idx;

int main()
&#123;
   scanf(&quot;%d%d&quot;,&amp;m,&amp;n);
   for(int i=0; i&lt;n; i++)&#123;
      scanf(&quot;%d%d%d&quot;,&amp;w,&amp;v,&amp;g);
      if(!mp[g]) mp[g] = ++idx;
      gg = mp[g];
      gr[gg][num[gg]].weight = w;
      gr[gg][num[gg]].value  = v;
      num[gg] += 1;
   &#125;
   for(int i=1; i&lt;=idx; i++)&#123;
      for(int j=m; j&gt;=0; j--)&#123;
         for(int k=0; k&lt;num[i]; k++)&#123;
            if(j &gt;= gr[i][k].weight)&#123;
               dp[j] = std::max(dp[j],dp[j-gr[i][k].weight]+gr[i][k].value);
            &#125;
         &#125;
      &#125;
   &#125;
   printf(&quot;%d&quot;,dp[m]);
   return 0;
&#125;
</code></pre>
<h2 id="洛谷-p1064-noip2006-提高组-金明的预算方案"><a class="markdownIt-Anchor" href="#洛谷-p1064-noip2006-提高组-金明的预算方案"></a> 洛谷 P1064 [NOIP2006 提高组] 金明的预算方案</h2>
<p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1064">https://www.luogu.com.cn/problem/P1064</a></p>
<p>​<br />
#include <cstdio><br />
#include <iostream><br />
#include <cstring><br />
#include <algorithm><br />
#include <cmath><br />
#include <cstdlib><br />
#include <queue><br />
#include <map><br />
#include <set><br />
#include <stack><br />
#include <vector><br />
typedef long long LL;<br />
typedef std::pair&lt;int ,int&gt; PP;<br />
const int N = 3.2e4+5,M = 105;<br />
int va[N],ww[N],ex[N][3],zhu[N],dp[N];<br />
int n,m,z,idx,tv,tz,tf,tf2;</p>
<pre><code>int main()
&#123;
   scanf(&quot;%d%d&quot;,&amp;m,&amp;n);
   for(int i=1; i&lt;=n; i++)&#123;
      scanf(&quot;%d%d%d&quot;,&amp;va[i],&amp;ww[i],&amp;z);
      if(z) &#123;
         ex[z][0] += 1;
         ex[z][ex[z][0]] = i;
      &#125;else&#123;
         zhu[++idx] = i;
      &#125;
   &#125;
   for(int i=1; i&lt;=idx; i++)&#123;
      tz = zhu[i];
      for(int j=m; j&gt;=0; j--)&#123;
         tv = va[tz];
         if(j &gt;= tv) dp[j] = std::max(dp[j],dp[j-tv]+ww[tz]*va[tz]);
         if(ex[tz][0])&#123;
            tf = ex[tz][1];
            tv = va[tz] + va[tf];
            if(j &gt;= tv) dp[j] = std::max(dp[j],dp[j-tv]+ww[tz]*va[tz]+ww[tf]*va[tf]);
         &#125;
         if(ex[tz][0] &gt;= 2)&#123;
            tf2 = ex[tz][2];
            tv = va[tz]+va[tf2];
            if(j &gt;= tv) dp[j] = std::max(dp[j],dp[j-tv]+ww[tz]*va[tz]+ww[tf2]*va[tf2]);
            tv += va[tf];
            if(j &gt;= tv) dp[j] = std::max(dp[j],dp[j-tv]+ww[tz]*va[tz]+ww[tf2]*va[tf2]+ww[tf]*va[tf]);
         &#125;
      &#125;
   &#125;
   printf(&quot;%d&quot;,dp[m]);
   return 0;
&#125;
</code></pre>
<h2 id="洛谷-p5322-bjoi2019排兵布阵"><a class="markdownIt-Anchor" href="#洛谷-p5322-bjoi2019排兵布阵"></a> 洛谷 P5322 [BJOI2019]排兵布阵</h2>
<p>分组背包<br />
用dp[i] 记录总共派出i个人的时候，最大的得分<br />
<strong>1.准备</strong></p>
<blockquote>
<p>想办法构造一个cas[][]数组 记录第i个城堡可以打败j个玩家时刚好需要多少兵力。<br />
这样我们可以认为， <strong>每个城堡为一组</strong> ，每一组中有s个数据分别为:在城堡i，分别打败1,2,3…s个玩家[花费的兵力，得到的分数]</p>
</blockquote>
<p><strong>2.开始套分组背包模板</strong></p>
<blockquote>
<p>-&gt;for [1,2,3,4…n] 枚举所有的n个城堡:<br />
…-&gt;for[m,m-1…3,2,1] 倒序枚举派遣总人数:<br />
…/…-&gt;for[1,2,3,4…s] 枚举每个城堡的s组数据:<br />
…/…/…-&gt;dp[w] = std::max(dp[w], dp[w-cost]+gain);</p>
</blockquote>
<pre><code>#include &lt;iostream&gt;
#include &lt;cstdio&gt;
#include &lt;cstdlib&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;algorithm&gt;
#include &lt;string&gt;
#include &lt;queue&gt;
#include &lt;vector&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
typedef long long int LL;
const int INF = 0x7fffffff, SCF = 0x3fffffff;
const int N = 105, M = 2e4+4, MOD =  1000000007;
int ssa[N][N];//every enemy's solders send to castle i; 
int cas[N][N];//min solders number you send when you can beat j player at castle i;
int dp/*[N]*/[M];//max score you gain when castle = i and solders = j
int s,n,m,v;
int main()
&#123;
    scanf(&quot;%d%d%d&quot;,&amp;s,&amp;n,&amp;m);
    for(int i=1; i&lt;=s; i++)&#123;
        for(int j=1; j&lt;=n; j++)&#123;
            scanf(&quot;%d&quot;,&amp;ssa[j][i]);
        &#125;
    &#125;
    for(int i=1; i&lt;=n; i++)&#123;
        std::sort(ssa[i]+1,ssa[i]+s+1);
    &#125;
    for(int i=1; i&lt;=n; i++)&#123;
        for(int j=1; j&lt;=s; j++)&#123;
            int num = (ssa[i][j]&lt;&lt;1)+1;
            cas[i][j] = num;
            if(num &gt; m) break;
        &#125;
    &#125;
    //for(int i=0; i&lt;M; i++) dp[i] = -SCF;
    //dp[0] = 0;
    for(int i=1; i&lt;=n; i++)&#123;
        for(int w=m; w&gt;=0; w--)&#123;
            for(int j=0; j&lt;=s; j++)&#123;
                int gain = i*j, cost = cas[i][j];
                if(w-cost &lt; 0) break;
                dp[w] = std::max(dp[w], dp[w-cost]+gain);
            &#125;
        &#125;
    &#125;
    printf(&quot;%d&quot;,dp[m]);
    return 0;
&#125;
</code></pre>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90%E8%83%8C%E5%8C%85DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P5020%E8%B4%A7%E5%B8%81%E7%B3%BB%E7%BB%9F%20P1757%E9%80%9A%E5%A4%A9%E4%B9%8B%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85%20P1064[NOIP2006%20%E6%8F%90%E9%AB%98%E7%BB%84]%E9%87%91%E6%98%8E%E7%9A%84%E9%A2%84%E7%AE%97%E6%96%B9%E6%A1%88%20P5322%20[BJOI2019]%E6%8E%92%E5%85%B5%E5%B8%83%E9%98%B5/" data-id="cl2uhoedc004oe4j32lki5x9c" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DP/" rel="tag">DP</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-【记录】py文件怎么转成exe文件" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90%E8%AE%B0%E5%BD%95%E3%80%91py%E6%96%87%E4%BB%B6%E6%80%8E%E4%B9%88%E8%BD%AC%E6%88%90exe%E6%96%87%E4%BB%B6/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E3%80%90%E8%AE%B0%E5%BD%95%E3%80%91py%E6%96%87%E4%BB%B6%E6%80%8E%E4%B9%88%E8%BD%AC%E6%88%90exe%E6%96%87%E4%BB%B6/">【记录】py文件怎么转成exe文件.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E6%95%99%E7%BB%83%E6%88%91%E6%83%B3%E5%AD%A6%E6%8C%82%E8%BE%B9%E8%BA%B2%E7%89%9B/">教练我想学挂边躲牛</a>,<a class="article-category-link" href="/categories/%E6%95%99%E7%BB%83%E6%88%91%E6%83%B3%E5%AD%A6%E6%8C%82%E8%BE%B9%E8%BA%B2%E7%89%9B/%E6%9D%82%E4%B9%B1/">杂乱</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<p>其实转完了之后我也是啥也不会的状态，所有的操作仅仅是照葫芦画瓢</p>
<p>第一步：<br />
首先你要有 pyinstaller</p>
<p>第二步：<br />
打开cmd 输入pyinstaller -F --onefile 需要转换的文件<br />
这样就ok了</p>
<p>附带一些pyinstaller的用法（转自<a target="_blank" rel="noopener" href="https://blog.csdn.net/jirryzhang/article/details/78881512">https://blog.csdn.net/jirryzhang/article/details/78881512</a>）<br />
-F, –onefile 产生一个文件用于部署 (参见XXXXX).<br />
-D, –onedir 产生一个目录用于部署 (默认)<br />
-K, –tk 在部署时包含 TCL/TK<br />
-a, –ascii 不包含编码.在支持Unicode的python版本上默认包含所有的编码.<br />
-d, –debug 产生debug版本的可执行文件<br />
-w,–windowed,–noconsole 使用Windows子系统执行.当程序启动的时候不会打开命令行(只对Windows有效)<br />
-c,–nowindowed,–console 使用控制台子系统执行(默认)(只对Windows有效)<br />
-s,–strip 可执行文件和共享库将run through strip.注意Cygwin的strip往往使普通的win32 Dll无法使用.<br />
-X, –upx 如果有UPX安装(执行Configure.py时检测),会压缩执行文件(Windows系统中的DLL也会)(参见note)<br />
-o DIR, –out=DIR 指定spec文件的生成目录,如果没有指定,而且当前目录是PyInstaller的根目录,会自动创建一个用于输出(spec和生成的可执行文件)的目录.如果没有指定,而当前目录不是PyInstaller的根目录,则会输出到当前的目录下.<br />
-p DIR, –path=DIR 设置导入路径(和使用PYTHONPATH效果相似).可以用路径分割符(Windows使用分号,Linux使用冒号)分割,指定多个目录.也可以使用多个-p参数来设置多个导入路径<br />
–icon=&lt;FILE.ICO&gt; 将file.ico添加为可执行文件的资源(只对Windows系统有效)<br />
–icon=&lt;FILE.EXE,N&gt; 将file.exe的第n个图标添加为可执行文件的资源(只对Windows系统有效)<br />
-v FILE, –version=FILE 将verfile作为可执行文件的版本资源(只对Windows系统有效)<br />
-n NAME, –name=NAME 可选的项目(产生的spec的)名字.如果省略,第一个脚本的主文件名将作为spec的名字<br />
————————————————<br />
版权声明：本文为CSDN博主「jirryzhang」的原创文章<br />
原文链接：<a target="_blank" rel="noopener" href="https://blog.csdn.net/jirryzhang/article/details/78881512">https://blog.csdn.net/jirryzhang/article/details/78881512</a></p>
<p>pyinstaller -F -i icon.ico -w <a target="_blank" rel="noopener" href="http://sadf.py">sadf.py</a></p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90%E8%AE%B0%E5%BD%95%E3%80%91py%E6%96%87%E4%BB%B6%E6%80%8E%E4%B9%88%E8%BD%AC%E6%88%90exe%E6%96%87%E4%BB%B6/" data-id="cl2uhoedd004se4j3bh5rcq4r" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-可持久化线段树【主席树】可持久化并查集【主席树+并查集】" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E7%BA%BF%E6%AE%B5%E6%A0%91%E3%80%90%E4%B8%BB%E5%B8%AD%E6%A0%91%E3%80%91%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E5%B9%B6%E6%9F%A5%E9%9B%86%E3%80%90%E4%B8%BB%E5%B8%AD%E6%A0%91+%E5%B9%B6%E6%9F%A5%E9%9B%86%E3%80%91/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E7%BA%BF%E6%AE%B5%E6%A0%91%E3%80%90%E4%B8%BB%E5%B8%AD%E6%A0%91%E3%80%91%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E5%B9%B6%E6%9F%A5%E9%9B%86%E3%80%90%E4%B8%BB%E5%B8%AD%E6%A0%91+%E5%B9%B6%E6%9F%A5%E9%9B%86%E3%80%91/">可持久化线段树【主席树】可持久化并查集【主席树+并查集】.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E6%80%9D%E6%83%B3or%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">思想or数据结构</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="笼统的主席树原理"><a class="markdownIt-Anchor" href="#笼统的主席树原理"></a> 笼统的主席树原理</h2>
<p>众所周知， 主席树是可以持久化的， 换言之你能知道你所维护信息的所有历史状态。 主席树是这样做的：</p>
<h4 id="1"><a class="markdownIt-Anchor" href="#1"></a> 1.</h4>
<p>首先建一颗朴素的线段树，代表初始状态 <strong>(下图黑色)</strong> ， 也就是第0次操作后的状态。</p>
<h4 id="tipa"><a class="markdownIt-Anchor" href="#tipa"></a> tipA:</h4>
<p>你每次只对一个叶子节点的数据进行更新，所以相当于更改了树上的一条链。</p>
<h4 id="2"><a class="markdownIt-Anchor" href="#2"></a> 2.</h4>
<p>我们不在原来的树上修改,而是创建若干个新的节点组成一条链代表树中修改后的各个节点 <strong>(下图红色)</strong> ，然后直接把这条链糊到树上，<br />
并且让新链中的每个节点都连好它在树中应该连的节点 <strong>(下图蓝色)</strong> 。</p>
<h4 id="tipb"><a class="markdownIt-Anchor" href="#tipb"></a> tipB:</h4>
<p>你会发现只要交换新旧链， 就可以得到两颗完整的树</p>
<h4 id="tipc"><a class="markdownIt-Anchor" href="#tipc"></a> tipC:</h4>
<p>你还会发现：在每次更新中添加的新链，都会包含树的根节点，所以你只需要记录下第[0 - N]次操作后的树的根节点，就可以通过某一个根节点得到特定历史版本的树。<br />
（0次操作后的根节点是黑色树根， 1次操作后的根节点是红色树根）</p>
<h4 id="3"><a class="markdownIt-Anchor" href="#3"></a> 3.</h4>
<p>然 后 随 便 van van ， 主 席 树 就 学 完 了。</p>
<h4 id="4"><a class="markdownIt-Anchor" href="#4"></a> <s>4.</s></h4>
<p><s>然后我们就可以滚到别的题解上爬了</s><br />
![在这里插入图片描述](https://img-<br />
<a target="_blank" rel="noopener" href="http://blog.csdnimg.cn/e988fd004312427286dd76e4a36b37e5.png?x-oss-">blog.csdnimg.cn/e988fd004312427286dd76e4a36b37e5.png?x-oss-</a><br />
process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAU3RhcnNXaGlzcGVy,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center)</p>
<h2 id="主席树-luogucomcn-的主席树板子"><a class="markdownIt-Anchor" href="#主席树-luogucomcn-的主席树板子"></a> 主席树 <a target="_blank" rel="noopener" href="http://luogu.com.cn">luogu.com.cn</a> 的主席树板子</h2>
<p>纯区间第K大<br />
区间[r - (l - 1)] 相当于只插入了[l - r] 然后直接找。</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">2e5</span>+<span class="number">4</span>;</span><br><span class="line"><span class="type">int</span> lst[N]<span class="comment">/*原序列*/</span>, srt[N]<span class="comment">/*排序数组*/</span>, root[N]<span class="comment">/*记录树根*/</span>;</span><br><span class="line"><span class="type">int</span> sum[N&lt;&lt;<span class="number">5</span>], L[N&lt;&lt;<span class="number">5</span>], R[N&lt;&lt;<span class="number">5</span>];</span><br><span class="line"><span class="type">int</span> n, m, ql, qr, k, idx, sn;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">build</span><span class="params">(<span class="type">int</span> l, <span class="type">int</span> r)</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> rt = ++idx, mid = (l + r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(l &lt; r)&#123;</span><br><span class="line">        L[rt] = <span class="built_in">build</span>(l, mid);</span><br><span class="line">        R[rt] = <span class="built_in">build</span>(mid + <span class="number">1</span>, r);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> rt;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">update</span><span class="params">(<span class="type">int</span> pre, <span class="type">int</span> l, <span class="type">int</span> r, <span class="type">int</span> k)</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> rt = ++idx, mid = (l + r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    L[rt] = L[pre], R[rt] = R[pre], sum[rt] = sum[pre] + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(l &lt; r)&#123;</span><br><span class="line">        <span class="keyword">if</span>(k &lt;= mid) L[rt] = <span class="built_in">update</span>(L[pre], l, mid, k);</span><br><span class="line">        <span class="keyword">else</span> R[rt] = <span class="built_in">update</span>(R[pre], mid + <span class="number">1</span>, r, k);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> rt;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">query</span><span class="params">(<span class="type">int</span> ql, <span class="type">int</span> qr, <span class="type">int</span> l, <span class="type">int</span> r, <span class="type">int</span> k)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>( l &gt;= r) <span class="keyword">return</span> l;</span><br><span class="line">    <span class="type">int</span> num = sum[L[qr]] - sum[L[ql]], mid = (l + r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(num &gt;= k) <span class="keyword">return</span> <span class="built_in">query</span>(L[ql], L[qr], l, mid, k);</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">return</span> <span class="built_in">query</span>(R[ql], R[qr], mid + <span class="number">1</span>, r, k - num);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;n, &amp;m);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;lst[i]);</span><br><span class="line">        srt[i] = lst[i];</span><br><span class="line">    &#125;</span><br><span class="line">    std::<span class="built_in">sort</span>(srt + <span class="number">1</span>, srt + <span class="number">1</span> + n);</span><br><span class="line">    sn = std::<span class="built_in">unique</span>(srt + <span class="number">1</span>, srt + <span class="number">1</span> + n) - srt - <span class="number">1</span>;</span><br><span class="line">    root[<span class="number">0</span>] = <span class="built_in">build</span>(<span class="number">1</span>, sn);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">        k = std::<span class="built_in">lower_bound</span>(srt + <span class="number">1</span>, srt + <span class="number">1</span> + sn, lst[i]) - srt;</span><br><span class="line">        root[i] = <span class="built_in">update</span>(root[i - <span class="number">1</span>], <span class="number">1</span>, sn, k);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(m --)&#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>, &amp;ql, &amp;qr, &amp;k);</span><br><span class="line">        n = <span class="built_in">query</span>(root[ql - <span class="number">1</span>], root[qr], <span class="number">1</span>, sn, k);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, srt[n]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="主席树并查集-luogucomcn-的可持久化并查集板子"><a class="markdownIt-Anchor" href="#主席树并查集-luogucomcn-的可持久化并查集板子"></a> 主席树+并查集 <a target="_blank" rel="noopener" href="http://luogu.com.cn">luogu.com.cn</a> 的可持久化并查集板子</h2>
<p>纯并查集</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">1e5</span> + <span class="number">4</span>, M = <span class="number">2e5</span> + <span class="number">4</span>;</span><br><span class="line"><span class="type">int</span> n, q, idx, x, y, op, xx, yy;</span><br><span class="line"><span class="type">int</span> D[M &lt;&lt; <span class="number">5</span>], F[M &lt;&lt; <span class="number">5</span>], L[M &lt;&lt; <span class="number">5</span>], R[M &lt;&lt; <span class="number">5</span>], E[M];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">build</span><span class="params">(<span class="type">int</span> l, <span class="type">int</span> r)</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> rt = ++idx;</span><br><span class="line">    <span class="keyword">if</span>(l == r) &#123; F[rt] = l, D[rt] = <span class="number">1</span>; <span class="keyword">return</span> rt; &#125;</span><br><span class="line">    <span class="type">int</span> mid = (l + r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    L[rt] = <span class="built_in">build</span>(l, mid);</span><br><span class="line">    R[rt] = <span class="built_in">build</span>(mid + <span class="number">1</span>, r);</span><br><span class="line">    <span class="keyword">return</span> rt;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">update</span><span class="params">(<span class="type">int</span> pre, <span class="type">int</span> l, <span class="type">int</span> r, <span class="type">int</span> k, <span class="type">int</span> f)</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> rt = ++idx;</span><br><span class="line">    <span class="keyword">if</span>(l == r)&#123;</span><br><span class="line">        D[rt] = D[pre];</span><br><span class="line">        F[rt] = f;</span><br><span class="line">        <span class="keyword">return</span> rt;</span><br><span class="line">    &#125;</span><br><span class="line">    L[rt] = L[pre], R[rt] = R[pre];</span><br><span class="line">    <span class="type">int</span> mid = (l + r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(k &lt;= mid) L[rt] = <span class="built_in">update</span>(L[pre], l, mid, k , f);</span><br><span class="line">    <span class="keyword">else</span> R[rt] = <span class="built_in">update</span>(R[pre], mid + <span class="number">1</span>, r, k, f);</span><br><span class="line">    <span class="keyword">return</span> rt;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">query</span><span class="params">(<span class="type">int</span> rt, <span class="type">int</span> l, <span class="type">int</span> r, <span class="type">int</span> k)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(l == r) <span class="keyword">return</span> rt;</span><br><span class="line">    <span class="type">int</span> mid = (l + r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(k &lt;= mid) <span class="keyword">return</span> <span class="built_in">query</span>(L[rt], l, mid, k);</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">query</span>(R[rt], mid + <span class="number">1</span>, r, k);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">cd</span><span class="params">(<span class="type">int</span> rt, <span class="type">int</span> l, <span class="type">int</span> r, <span class="type">int</span> k)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(l == r) &#123;D[rt] += <span class="number">1</span>; <span class="keyword">return</span> ;&#125;</span><br><span class="line">    <span class="type">int</span> mid = (l + r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(k &lt;= mid) <span class="built_in">cd</span>(L[rt], l, mid, k);</span><br><span class="line">    <span class="keyword">else</span> <span class="built_in">cd</span>(R[rt], mid + <span class="number">1</span>, r, k);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">ffind</span><span class="params">(<span class="type">int</span> rt, <span class="type">int</span> x)</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> t = <span class="built_in">query</span>(rt, <span class="number">1</span>, n, x);</span><br><span class="line">    <span class="keyword">if</span>(x == F[t]) <span class="keyword">return</span> t;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">ffind</span>(rt, F[t]);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;n, &amp;q);</span><br><span class="line">    E[<span class="number">0</span>] = <span class="built_in">build</span>(<span class="number">1</span>, n);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=q; i++)&#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;op);</span><br><span class="line">        <span class="keyword">if</span>(op == <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;x, &amp;y);</span><br><span class="line">            E[i] = E[i - <span class="number">1</span>];</span><br><span class="line">            xx = <span class="built_in">ffind</span>(E[i], x), yy = <span class="built_in">ffind</span>(E[i], y);</span><br><span class="line">            <span class="keyword">if</span>(D[xx] &gt; D[yy]) std::<span class="built_in">swap</span>(xx, yy);</span><br><span class="line">            E[i] = <span class="built_in">update</span>(E[i - <span class="number">1</span>], <span class="number">1</span>, n, F[xx], F[yy]);</span><br><span class="line">            <span class="keyword">if</span>(D[xx] + <span class="number">1</span> &gt; D[yy]) <span class="built_in">cd</span>(E[i], <span class="number">1</span>, n, F[yy]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(op == <span class="number">2</span>)&#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;x);</span><br><span class="line">            E[i] = E[x];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(op == <span class="number">3</span>)&#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;x, &amp;y);</span><br><span class="line">            E[i] = E[i - <span class="number">1</span>];</span><br><span class="line">            xx = <span class="built_in">ffind</span>(E[i], x), yy = <span class="built_in">ffind</span>(E[i], y);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, F[xx] == F[yy] ? <span class="number">1</span> : <span class="number">0</span>);</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E7%BA%BF%E6%AE%B5%E6%A0%91%E3%80%90%E4%B8%BB%E5%B8%AD%E6%A0%91%E3%80%91%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E5%B9%B6%E6%9F%A5%E9%9B%86%E3%80%90%E4%B8%BB%E5%B8%AD%E6%A0%91+%E5%B9%B6%E6%9F%A5%E9%9B%86%E3%80%91/" data-id="cl2uhoedf0050e4j31dwz6vqb" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%BA%BF%E6%AE%B5%E6%A0%91/" rel="tag">线段树</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-数据预处理  sklearn 或者别的库" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E6%95%B0%E6%8D%AE%E9%A2%84%E5%A4%84%E7%90%86%20%20sklearn%20%E6%88%96%E8%80%85%E5%88%AB%E7%9A%84%E5%BA%93/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E6%95%B0%E6%8D%AE%E9%A2%84%E5%A4%84%E7%90%86%20%20sklearn%20%E6%88%96%E8%80%85%E5%88%AB%E7%9A%84%E5%BA%93/">数据预处理  sklearn 或者别的库.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E6%95%99%E7%BB%83%E6%88%91%E6%83%B3%E5%AD%A6%E6%8C%82%E8%BE%B9%E8%BA%B2%E7%89%9B/">教练我想学挂边躲牛</a>,<a class="article-category-link" href="/categories/%E6%95%99%E7%BB%83%E6%88%91%E6%83%B3%E5%AD%A6%E6%8C%82%E8%BE%B9%E8%BA%B2%E7%89%9B/%E7%9E%8E%E5%AD%A6%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/">瞎学机器学习</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="无量纲化"><a class="markdownIt-Anchor" href="#无量纲化"></a> 无量纲化</h2>
<p>sklearn.preprocessing.MinMaxScaler<br />
数据归一化<br />
（数据-最小值）/极差 把数据限制在0-1之间 范围可以改 feature_range</p>
<p>​</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> sklearn.preprocessing <span class="keyword">import</span> MinMaxScaler</span><br><span class="line"></span><br><span class="line">data = [[-<span class="number">10</span>,<span class="number">16</span>],[-<span class="number">5</span>,<span class="number">32</span>],[<span class="number">0</span>,<span class="number">48</span>],[<span class="number">5</span>,<span class="number">64</span>]]</span><br><span class="line"></span><br><span class="line">scaler = MinMaxScaler(feature_range = [<span class="number">0</span>,<span class="number">2</span>])</span><br><span class="line">scaler = scaler.fit(data)</span><br><span class="line"><span class="comment">#scaler = scaler.partial_fit(data)</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#进行数据归一化</span></span><br><span class="line">result = scaler.transform(data)</span><br><span class="line"></span><br><span class="line"><span class="comment">#利用归一化结果还原原数据</span></span><br><span class="line">origin = scaler.inverse_transform(result)</span><br><span class="line"></span><br><span class="line"><span class="comment">#一步</span></span><br><span class="line">result2 = scaler.fit_transform(data)</span><br></pre></td></tr></table></figure>
<p>​</p>
<p>sklearn.preprocessing.StandardScaler<br />
数据标准化<br />
中心化后 x-均值（均值为零）/标准差<br />
之后满足均值0方差1 的正态分布</p>
<p>​</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> sklearn.preprocessing <span class="keyword">import</span> StandardScaler</span><br><span class="line"></span><br><span class="line">data = [[-<span class="number">10</span>,<span class="number">16</span>],[-<span class="number">5</span>,<span class="number">32</span>],[<span class="number">0</span>,<span class="number">48</span>],[<span class="number">5</span>,<span class="number">64</span>]]</span><br><span class="line"></span><br><span class="line">scaler = StandardScaler()</span><br><span class="line">scaler.fit(data)</span><br><span class="line"></span><br><span class="line"><span class="comment">#mean_均值, var_方差</span></span><br><span class="line"><span class="built_in">print</span>(scaler.mean_, scaler.var_)</span><br><span class="line"></span><br><span class="line">result = scaler.transform(data)</span><br><span class="line"><span class="built_in">print</span>(result.mean(), result.std())</span><br><span class="line"><span class="comment">#转化后服从均值为0方差为1的正态分布</span></span><br><span class="line"></span><br><span class="line">origin =  scaler.inverse_transform(result)</span><br><span class="line"></span><br><span class="line"><span class="comment">#一步</span></span><br><span class="line">result2 = scaler.fit_transform(data)</span><br></pre></td></tr></table></figure>
<p>sklearn.preprocessing.MaxAbsScaler<br />
所有数据/abs（绝对值最大的值）</p>
<p>​</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> sklearn.preprocessing <span class="keyword">import</span> MaxAbsScaler</span><br><span class="line"></span><br><span class="line">data = [[-<span class="number">10</span>,<span class="number">8</span>],[-<span class="number">5</span>,<span class="number">16</span>],[<span class="number">0</span>,<span class="number">24</span>],[<span class="number">5</span>,<span class="number">32</span>]]</span><br><span class="line"></span><br><span class="line">scaler = MaxAbsScaler()</span><br><span class="line">scaler = scaler.fit(data)</span><br><span class="line">result = scaler.transform(data)</span><br><span class="line"></span><br><span class="line">origin = scaler.inverse_transform(result)</span><br><span class="line"></span><br><span class="line"><span class="comment">#一步</span></span><br><span class="line">result2 = scaler.fit_transform(data)</span><br></pre></td></tr></table></figure>
<h2 id="缺失值"><a class="markdownIt-Anchor" href="#缺失值"></a> 缺失值</h2>
<p>​</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> pandas <span class="keyword">as</span> pd</span><br><span class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</span><br><span class="line"></span><br><span class="line"><span class="comment"># 从excel表导入数据</span></span><br><span class="line">df_t = pd.read_excel(<span class="string">r&#x27;D:\EdgeDownloadPlace\3dd40612152202ee8440f82a3d277008\train.xlsx&#x27;</span>)</span><br><span class="line"></span><br><span class="line"><span class="built_in">print</span>(df_t.info())</span><br><span class="line"></span><br><span class="line"><span class="comment"># 提取列 所有</span></span><br><span class="line"><span class="built_in">print</span>(df_t.loc[:,<span class="string">&#x27;uid&#x27;</span>])</span><br><span class="line"></span><br><span class="line">arr_t_uid = df_t.loc[:,<span class="string">&#x27;uid&#x27;</span>].values</span><br><span class="line"></span><br><span class="line"><span class="comment">#转换成二维</span></span><br><span class="line">arr_t_uid = arr_t_uid.reshape(-<span class="number">1</span>,<span class="number">1</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment">#找到ca列中为？的行</span></span><br><span class="line">ca_wenhao =df_t[df_t.loc[:,<span class="string">&#x27;ca&#x27;</span>]==<span class="string">&#x27;?&#x27;</span>]</span><br><span class="line"></span><br><span class="line"><span class="comment">#替换ca列的？为x</span></span><br><span class="line">df_t[<span class="string">&#x27;ca&#x27;</span>][df_t[<span class="string">&#x27;ca&#x27;</span>]==<span class="string">&#x27;?&#x27;</span>] = <span class="string">&#x27;x&#x27;</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">print</span>(<span class="string">&#x27;中位数&#x27;</span>,df_t.loc[:,<span class="string">&#x27;age&#x27;</span>].median())</span><br><span class="line"><span class="built_in">print</span>(<span class="string">&#x27;平均数&#x27;</span>,df_t.loc[:,<span class="string">&#x27;age&#x27;</span>].mean())</span><br><span class="line"><span class="built_in">print</span>(<span class="string">&#x27;众数&#x27;</span>,df_t.loc[:,<span class="string">&#x27;age&#x27;</span>].mode())</span><br><span class="line">cnt =df_t.loc[:,<span class="string">&#x27;age&#x27;</span>].value_counts() <span class="comment">#把所有的值计数 降序排序</span></span><br><span class="line">idx = cnt.index <span class="comment">#结果降序排序</span></span><br></pre></td></tr></table></figure>
<p>​</p>
<p>此数据缺失值用？代表 ，直接把？换了。<br />
如果缺失值为nan 可以直接用pd.drowna() 或pd.fillna()</p>
<h2 id="编码-哑变量-处理分类数据用"><a class="markdownIt-Anchor" href="#编码-哑变量-处理分类数据用"></a> 编码 哑变量 ---- 处理分类数据用</h2>
<p>​</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> pandas <span class="keyword">as</span> pd</span><br><span class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</span><br><span class="line"><span class="keyword">from</span> sklearn.preprocessing <span class="keyword">import</span> LabelEncoder</span><br><span class="line"><span class="keyword">from</span> sklearn.preprocessing <span class="keyword">import</span> OrdinalEncoder</span><br><span class="line"><span class="keyword">from</span> sklearn.preprocessing <span class="keyword">import</span> OneHotEncoder</span><br><span class="line"></span><br><span class="line">df_t = pd.read_excel(<span class="string">r&#x27;D:\EdgeDownloadPlace\大数据比赛测试示例\训练集.xlsx&#x27;</span>)</span><br><span class="line"><span class="comment">#删掉 ‘Embarked’列有缺失值的行</span></span><br><span class="line">df_t.dropna(axis = <span class="number">0</span> , subset = [<span class="string">&#x27;Embarked&#x27;</span>], inplace = <span class="literal">True</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment">#一维</span></span><br><span class="line">LE = LabelEncoder()</span><br><span class="line">LElabel = LE.fit_transform(df_t[<span class="string">&#x27;Embarked&#x27;</span>].astype(np.<span class="built_in">str</span>))</span><br><span class="line"></span><br><span class="line"><span class="comment">#多维</span></span><br><span class="line">OE= OrdinalEncoder()</span><br><span class="line">OElabel = OE.fit_transform(df_t.loc[:,[<span class="string">&#x27;Sex&#x27;</span>,<span class="string">&#x27;Embarked&#x27;</span>]])</span><br><span class="line"></span><br><span class="line"><span class="comment">#独热编码</span></span><br><span class="line">OHE = OneHotEncoder(categories = <span class="string">&#x27;auto&#x27;</span>)</span><br><span class="line">OHElabel = OHE.fit_transform(df_t.loc[:,[<span class="string">&#x27;Sex&#x27;</span>,<span class="string">&#x27;Embarked&#x27;</span>]])</span><br><span class="line">df_ttt = pd.concat([df_t,pd.DataFrame(OHElabel.toarray())],axis = <span class="number">1</span>)</span><br><span class="line">df_ttt.columns = df_t.columns.tolist()+OHE.get_feature_names().tolist()</span><br><span class="line"></span><br><span class="line"><span class="built_in">print</span>(LE.classes_,OE.categories_,OHE.categories_,sep=<span class="string">&#x27;\n&#x27;</span>)</span><br><span class="line"></span><br><span class="line">rLE = LE.inverse_transform(LElabel)</span><br><span class="line">rOE = OE.inverse_transform(OElabel)</span><br><span class="line">rOHE = OHE.inverse_transform(OHElabel)</span><br></pre></td></tr></table></figure>
<h2 id="二值化-分箱-连续数据"><a class="markdownIt-Anchor" href="#二值化-分箱-连续数据"></a> 二值化 分箱 ----连续数据</h2>
<p>​</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> pandas <span class="keyword">as</span> pd</span><br><span class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</span><br><span class="line"><span class="keyword">from</span> sklearn.preprocessing <span class="keyword">import</span> Binarizer</span><br><span class="line"><span class="keyword">from</span> sklearn.preprocessing <span class="keyword">import</span> KBinsDiscretizer</span><br><span class="line"></span><br><span class="line">df_t = pd.read_excel(<span class="string">r&#x27;D:\EdgeDownloadPlace\大数据比赛测试示例\训练集.xlsx&#x27;</span>)</span><br><span class="line"></span><br><span class="line">df_t.fillna(df_t.loc[:,<span class="string">&#x27;Age&#x27;</span>].value_counts().index[<span class="number">0</span>],axis = <span class="number">1</span>,inplace = <span class="literal">True</span>)</span><br><span class="line">age_t = df_t[<span class="string">&#x27;Age&#x27;</span>].values.reshape(-<span class="number">1</span>,<span class="number">1</span>)</span><br><span class="line"></span><br><span class="line">B = Binarizer(threshold= <span class="number">24</span>)</span><br><span class="line">result = B.fit_transform(age_t)</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">#参数 encode：ordinal onehot 参考分类</span></span><br><span class="line"><span class="comment">#参数 strategy： uniform 等宽分箱(平分特征)  quantile等位分箱(分箱后每箱数量一致)  kmeans按聚类分箱</span></span><br><span class="line">KBD_ordinal = KBinsDiscretizer(n_bins = <span class="number">5</span>, encode = <span class="string">&#x27;ordinal&#x27;</span>, strategy= <span class="string">&#x27;uniform&#x27;</span>)</span><br><span class="line">KBDresult_ordinal = KBD_ordinal.fit_transform(age_t)</span><br><span class="line"><span class="built_in">print</span>(KBDresult_ordinal.ravel())<span class="comment">#ravel()的作用是降维</span></span><br><span class="line"></span><br><span class="line">KBD_onehot = KBinsDiscretizer(n_bins = <span class="number">5</span>, encode = <span class="string">&#x27;onehot&#x27;</span>, strategy= <span class="string">&#x27;uniform&#x27;</span>)</span><br><span class="line">KBDresult_onehot = KBD_onehot.fit_transform(age_t)</span><br><span class="line"><span class="built_in">print</span>(KBDresult_onehot.toarray())</span><br></pre></td></tr></table></figure>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E6%95%B0%E6%8D%AE%E9%A2%84%E5%A4%84%E7%90%86%20%20sklearn%20%E6%88%96%E8%80%85%E5%88%AB%E7%9A%84%E5%BA%93/" data-id="cl2uhoedg0054e4j3gjn96u93" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/" rel="tag">机器学习</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-学习在ECS上实现定期执行在学校官网发帖子签到的py脚本" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E5%AD%A6%E4%B9%A0%E5%9C%A8ECS%E4%B8%8A%E5%AE%9E%E7%8E%B0%E5%AE%9A%E6%9C%9F%E6%89%A7%E8%A1%8C%E5%9C%A8%E5%AD%A6%E6%A0%A1%E5%AE%98%E7%BD%91%E5%8F%91%E5%B8%96%E5%AD%90%E7%AD%BE%E5%88%B0%E7%9A%84py%E8%84%9A%E6%9C%AC/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E5%AD%A6%E4%B9%A0%E5%9C%A8ECS%E4%B8%8A%E5%AE%9E%E7%8E%B0%E5%AE%9A%E6%9C%9F%E6%89%A7%E8%A1%8C%E5%9C%A8%E5%AD%A6%E6%A0%A1%E5%AE%98%E7%BD%91%E5%8F%91%E5%B8%96%E5%AD%90%E7%AD%BE%E5%88%B0%E7%9A%84py%E8%84%9A%E6%9C%AC/">学习在ECS上实现定期执行在学校官网发帖子签到的py脚本.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E6%95%99%E7%BB%83%E6%88%91%E6%83%B3%E5%AD%A6%E6%8C%82%E8%BE%B9%E8%BA%B2%E7%89%9B/">教练我想学挂边躲牛</a>,<a class="article-category-link" href="/categories/%E6%95%99%E7%BB%83%E6%88%91%E6%83%B3%E5%AD%A6%E6%8C%82%E8%BE%B9%E8%BA%B2%E7%89%9B/%E7%88%AC%E8%99%AB/">爬虫</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<p><strong>本文不作为较专业的资料，仅为萌新不专业的试水和踩坑</strong></p>
<h2 id="1编写签到脚本"><a class="markdownIt-Anchor" href="#1编写签到脚本"></a> 1.编写签到脚本</h2>
<p>从这个环节开始我就遇到了许多问题，比如可以复制cookie实现签到，但不会获取cooike<br />
实际上直到现在写博客，我始终没有做到完整地吧所需要的cookie提取出来，对于爬虫也是一知半解</p>
<p>直接上误打误撞写出来的拉跨代码（部分内容隐蔽或更改）：</p>
<p>​</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> requests</span><br><span class="line"><span class="keyword">import</span> time</span><br><span class="line"></span><br><span class="line">url=<span class="string">&#x27;在学校官网登录请求的url&#x27;</span></span><br><span class="line">header=&#123;</span><br><span class="line">        <span class="string">&#x27;Referer&#x27;</span>: <span class="string">&#x27;secret&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;User-Agent&#x27;</span>: <span class="string">&#x27;mystery&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;Content-Type&#x27;</span>: <span class="string">&#x27;application/x-www-form-urlencoded&#x27;</span></span><br><span class="line">    &#125;</span><br><span class="line">data=&#123;</span><br><span class="line">        <span class="string">&#x27;IPT_LOGINUSERNAME&#x27;</span>: <span class="string">&#x27;what?&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;IPT_LOGINPASSWORD&#x27;</span>: <span class="string">&#x27;you don\&#x27;t know&#x27;</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">session=requests.session()</span><br><span class="line">res=session.post(url,headers=header,data=data)</span><br><span class="line"></span><br><span class="line">posturl=<span class="string">&#x27;发帖子请求的url&#x27;</span></span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">headersx=&#123;</span><br><span class="line">        <span class="string">&#x27;Content-Type&#x27;</span>: <span class="string">&#x27;application/x-www-form-urlencoded&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;Referer&#x27;</span>: <span class="string">&#x27;mytsery&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;User-Agent&#x27;</span>: <span class="string">&#x27;jsadsadfsadfasd&#x27;</span>,</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">datax=&#123;</span><br><span class="line">        <span class="string">&#x27;opt&#x27;</span>: <span class="string">&#x27;toreply&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;frompage&#x27;</span>: <span class="string">&#x27;common&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;forumid&#x27;</span>:<span class="string">&#x27;3743&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;threadid&#x27;</span>:<span class="string">&#x27;114775&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;parentid&#x27;</span>:<span class="string">&#x27;239973&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;type&#x27;</span>: <span class="string">&#x27;0&#x27;</span>,</span><br><span class="line">        <span class="string">&#x27;subject&#x27;</span>:<span class="string">&#x27;帖子标题的一些内容&#x27;</span>.encode(<span class="string">&quot;gbk&quot;</span>),</span><br><span class="line">        <span class="string">&#x27;body&#x27;</span>: <span class="string">&#x27;&lt;p&gt;学号 某某签到&lt;/p&gt;&#x27;</span>.encode(<span class="string">&quot;gbk&quot;</span>)<span class="comment">#编码格式一定要换，否则发出乱码</span></span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">resx=session.post(posturl,headers=headersx,data=datax)</span><br><span class="line"></span><br><span class="line"><span class="comment">#相当于一个日志</span></span><br><span class="line"><span class="keyword">with</span> <span class="built_in">open</span>(<span class="string">&#x27;journal.txt&#x27;</span>,<span class="string">&#x27;a&#x27;</span>) <span class="keyword">as</span> f:<span class="comment">#这是在本地写的，放在服务器上要使用绝对路径，否则会在根目录创建文件</span></span><br><span class="line">    string=<span class="string">&#x27;&#x27;</span></span><br><span class="line">    tm=time.localtime()</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">6</span>):</span><br><span class="line">        string+=<span class="built_in">str</span>(tm[i])+<span class="string">&#x27; &#x27;</span></span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        string+=<span class="string">&#x27;OVER \n&#x27;</span></span><br><span class="line">    f.write(string)</span><br></pre></td></tr></table></figure>
<p>​</p>
<h2 id="2在ecs上令其定时执行"><a class="markdownIt-Anchor" href="#2在ecs上令其定时执行"></a> 2.在ECS上令其定时执行</h2>
<p>我的云服务器装的乌班图系统</p>
<p>先通过以下操作测试了一下py文件是否能在云服务器上运行，且运行成功</p>
<blockquote>
<p>python3 签到文件</p>
</blockquote>
<p>然后通过第一行的操作打开控制定时执行的文件，添加内容，最后两行是我新添加的内容(排版不是很好，服务器上看是很清晰的)。<br />
关于怎样设置执行时间见传送门：<a target="_blank" rel="noopener" href="https://www.runoob.com/linux/linux-comm-crontab.html">https://www.runoob.com/linux/linux-comm-crontab.html</a></p>
<blockquote>
<p>vi /etc/corntab</p>
</blockquote>
<blockquote>
<h1 id="m-h-dom-mon-dow-user-command"><a class="markdownIt-Anchor" href="#m-h-dom-mon-dow-user-command"></a> m h dom mon dow user command</h1>
<p>17 * * * * root cd / &amp;&amp; run-parts --report /etc/cron.hourly<br />
25 6 * * * root test -x /usr/sbin/anacron || ( cd / &amp;&amp; run-parts --report<br />
/etc/cron.daily )<br />
47 6 * * 7 root test -x /usr/sbin/anacron || ( cd / &amp;&amp; run-parts --report<br />
/etc/cron.weekly )<br />
52 6 1 * * root test -x /usr/sbin/anacron || ( cd / &amp;&amp; run-parts --report<br />
/etc/cron.monthly )<br />
0 14 * * 3 root /usr/bin/python3.6 /home/signIn195C/login195C.py<br />
0 10 * * 5 root /usr/bin/python3.6 /home/signIn195C/login195C.py</p>
</blockquote>
<h2 id="注意"><a class="markdownIt-Anchor" href="#注意"></a> 注意</h2>
<p>python脚本若要建立（或写入）文件一定要使用绝对路径。笔者手动执行程序时会在脚本所在的目录建立（或写入）文件，但自动执行时文件会在根目录建立（或写入）</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E5%AD%A6%E4%B9%A0%E5%9C%A8ECS%E4%B8%8A%E5%AE%9E%E7%8E%B0%E5%AE%9A%E6%9C%9F%E6%89%A7%E8%A1%8C%E5%9C%A8%E5%AD%A6%E6%A0%A1%E5%AE%98%E7%BD%91%E5%8F%91%E5%B8%96%E5%AD%90%E7%AD%BE%E5%88%B0%E7%9A%84py%E8%84%9A%E6%9C%AC/" data-id="cl2uhoedi0058e4j3eucy4ge7" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/linux/" rel="tag">linux</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E6%9C%8D%E5%8A%A1%E5%99%A8/" rel="tag">服务器</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%88%AC%E8%99%AB/" rel="tag">爬虫</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-欧拉函数" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0/">欧拉函数.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E6%95%B0%E8%AE%BA/">数论</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">find_prime</span><span class="params">(<span class="type">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">memset</span>(isprime,<span class="number">0</span>,<span class="built_in">sizeof</span>(isprime));</span><br><span class="line">    sp = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">2</span>;i &lt;= n;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(!isprime[i])</span><br><span class="line">        &#123;</span><br><span class="line">            prime[++sp] = i;</span><br><span class="line">            isprime[i] = i;</span><br><span class="line">            phi[i] = i<span class="number">-1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>;j &lt;= sp &amp;&amp; i * prime[j] &lt;= n;j++) &#123;</span><br><span class="line">            isprime[i*prime[j]] = prime[j];</span><br><span class="line">            <span class="keyword">if</span>(prime[j] &gt;= isprime[i]) &#123;</span><br><span class="line">                phi[i*prime[j]] = phi[i]*prime[j];</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            phi[i*prime[j]] = phi[i]*(prime[j]<span class="number">-1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0/" data-id="cl2uhoedj005ce4j35xc2ha35" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E6%95%B0%E8%AE%BA/" rel="tag">数论</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-破事水，一道泯若众题区间dp The Sports Festival" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E7%A0%B4%E4%BA%8B%E6%B0%B4%EF%BC%8C%E4%B8%80%E9%81%93%E6%B3%AF%E8%8B%A5%E4%BC%97%E9%A2%98%E5%8C%BA%E9%97%B4dp%20The%20Sports%20Festival/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E7%A0%B4%E4%BA%8B%E6%B0%B4%EF%BC%8C%E4%B8%80%E9%81%93%E6%B3%AF%E8%8B%A5%E4%BC%97%E9%A2%98%E5%8C%BA%E9%97%B4dp%20The%20Sports%20Festival/">破事水，一道泯若众题区间dp The Sports Festival.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/DP/">DP</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="the-sports-festival"><a class="markdownIt-Anchor" href="#the-sports-festival"></a> The Sports Festival</h2>
<h4 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h4>
<p>给 你 一 个 序 列 ( 数 据 可 重 复 ) ， 你 可 以 将 其 任 意 排 序 ， 最 小 化 Σ i = 1 n ( 前 i 个 数 的 极<br />
差 ) 给你一个序列(数据可重复)， 你可以将其任意排序， 最小化 \\ \Sigma_{i = 1} ^ n (前i个数的极差)<br />
给你一个序列(数据可重复)，你可以将其任意排序，最小化Σi=1n​(前i个数的极差)</p>
<h4 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h4>
<p>0.排一下序<br />
1.首先我们不可能先选一个最大的，再选一个最小的， 如果这样选就得到了最大值， 就g了， 除非数据特殊<br />
2.那我们肯定是要循序渐进一点点增大极差， 那就必须要选定某一个点开始， 然后慢慢把范围往两边阔<br />
3.那我们直接一波区间dp求出所有的情况并选个最小的就行了</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> int long long</span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">2005</span>;</span><br><span class="line"><span class="type">int</span> dp[N][N], x[N], n;</span><br><span class="line"><span class="function"><span class="type">signed</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>, &amp;n);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i ++) <span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>, &amp;x[i]);</span><br><span class="line">    std::<span class="built_in">sort</span>(x + <span class="number">1</span>, x + <span class="number">1</span> + n);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> s = <span class="number">1</span>; s &lt; n; s ++) <span class="keyword">for</span>(<span class="type">int</span> st = <span class="number">1</span>, ed; (ed = st + s) &lt;= n; st ++)&#123;</span><br><span class="line">        dp[st][ed] = std::<span class="built_in">min</span>(dp[st + <span class="number">1</span>][ed], dp[st][ed - <span class="number">1</span>]) + x[ed] - x[st];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%lld&quot;</span>, dp[<span class="number">1</span>][n]);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E7%A0%B4%E4%BA%8B%E6%B0%B4%EF%BC%8C%E4%B8%80%E9%81%93%E6%B3%AF%E8%8B%A5%E4%BC%97%E9%A2%98%E5%8C%BA%E9%97%B4dp%20The%20Sports%20Festival/" data-id="cl2uhoedm005oe4j3eiki8bsg" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DP/" rel="tag">DP</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-线段树 ~乱 ------------------------阿巴阿巴阿巴" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E7%BA%BF%E6%AE%B5%E6%A0%91%20~%E4%B9%B1%20------------------------%E9%98%BF%E5%B7%B4%E9%98%BF%E5%B7%B4%E9%98%BF%E5%B7%B4/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E7%BA%BF%E6%AE%B5%E6%A0%91%20~%E4%B9%B1%20------------------------%E9%98%BF%E5%B7%B4%E9%98%BF%E5%B7%B4%E9%98%BF%E5%B7%B4/">线段树 ~乱 ------------------------阿巴阿巴阿巴.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E6%80%9D%E6%83%B3or%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">思想or数据结构</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn=<span class="number">5e4</span>+<span class="number">4</span>;</span><br><span class="line"><span class="type">int</span> n,q,tt;</span><br><span class="line"><span class="type">int</span> mmx,mmn;</span><br><span class="line"><span class="type">int</span> cow[maxn];</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Node</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> mx,mn,l,r;</span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">getMid</span><span class="params">()</span> </span>&#123; <span class="keyword">return</span> (l+r) &gt;&gt; <span class="number">1</span>; &#125;</span><br><span class="line">&#125;treeN[maxn&lt;&lt;<span class="number">2</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">getMid</span><span class="params">(<span class="type">int</span> l,<span class="type">int</span> r)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (l+r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">build</span><span class="params">(<span class="type">int</span> l,<span class="type">int</span> r,<span class="type">int</span> root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    treeN[root].l=l; treeN[root].r=r;</span><br><span class="line">    <span class="keyword">if</span>(l==r)</span><br><span class="line">    &#123;</span><br><span class="line">        treeN[root].mx=cow[l];</span><br><span class="line">        treeN[root].mn=cow[l];</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="type">int</span> mmd=<span class="built_in">getMid</span>(l,r);</span><br><span class="line">    <span class="built_in">build</span>(l,mmd,root&lt;&lt;<span class="number">1</span>);</span><br><span class="line">    <span class="built_in">build</span>(mmd+<span class="number">1</span>,r,(root&lt;&lt;<span class="number">1</span>)+<span class="number">1</span>);</span><br><span class="line">    treeN[root].mx=std::<span class="built_in">max</span>(treeN[root&lt;&lt;<span class="number">1</span>].mx,treeN[(root&lt;&lt;<span class="number">1</span>)+<span class="number">1</span>].mx);</span><br><span class="line">    treeN[root].mn=std::<span class="built_in">min</span>(treeN[root&lt;&lt;<span class="number">1</span>].mn,treeN[(root&lt;&lt;<span class="number">1</span>)+<span class="number">1</span>].mn);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">getAns</span><span class="params">(<span class="type">int</span> l,<span class="type">int</span> r,<span class="type">int</span> root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(treeN[root].mn&gt;=mmn &amp;&amp; treeN[root].mx&lt;=mmx) <span class="keyword">return</span> ;</span><br><span class="line">    <span class="keyword">if</span>(treeN[root].l==l &amp;&amp; treeN[root].r==r)</span><br><span class="line">    &#123;</span><br><span class="line">        mmx=std::<span class="built_in">max</span>(mmx,treeN[root].mx);</span><br><span class="line">        mmn=std::<span class="built_in">min</span>(mmn,treeN[root].mn);</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="type">int</span> mmd=treeN[root].<span class="built_in">getMid</span>();</span><br><span class="line">    <span class="keyword">if</span>(r&lt;=mmd) <span class="built_in">getAns</span>(l,r,root&lt;&lt;<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span>(l&gt;mmd) <span class="built_in">getAns</span>(l,r,(root&lt;&lt;<span class="number">1</span>)+<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">getAns</span>(l,mmd,root&lt;&lt;<span class="number">1</span>);</span><br><span class="line">        <span class="built_in">getAns</span>(mmd+<span class="number">1</span>,r,(root&lt;&lt;<span class="number">1</span>)+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;n,&amp;q);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;cow[i]);</span><br><span class="line">    <span class="built_in">build</span>(<span class="number">1</span>,n,<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;q; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;n,&amp;tt);</span><br><span class="line">        mmx=<span class="number">-1</span>,mmn=<span class="number">1000005</span>;</span><br><span class="line">        <span class="built_in">getAns</span>(n,tt,<span class="number">1</span>);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,mmx-mmn);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​<br />
​<br />
​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> std::pair&lt;<span class="type">int</span> ,<span class="type">int</span> &gt; PP;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="type">int</span> n,m;</span><br><span class="line">ll ans;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxm=<span class="number">10005</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> BIG=<span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line"><span class="type">int</span> val[maxm];</span><br><span class="line">PP p[maxm];</span><br><span class="line"><span class="type">int</span> treen[maxm&lt;&lt;<span class="number">2</span>],lazy[maxm&lt;&lt;<span class="number">2</span>];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">getMid</span><span class="params">(<span class="type">int</span> a,<span class="type">int</span> b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (a+b)&gt;&gt;<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">cmp</span><span class="params">(PP a,PP b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(a.second==b.second) <span class="keyword">return</span> a.first &lt; b.first;</span><br><span class="line">    <span class="keyword">return</span> a.second &lt; b.second;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">build</span><span class="params">(<span class="type">int</span> l,<span class="type">int</span> r,<span class="type">int</span> rt)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    lazy[rt]=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span>(l==r) treen[rt]=val[l];</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="type">int</span> mid=<span class="built_in">getMid</span>(l,r);</span><br><span class="line">        <span class="built_in">build</span>(l,mid,rt&lt;&lt;<span class="number">1</span>);</span><br><span class="line">        <span class="built_in">build</span>(mid+<span class="number">1</span>,r,rt&lt;&lt;<span class="number">1</span>|<span class="number">1</span>);</span><br><span class="line">        treen[rt]=std::<span class="built_in">min</span>(treen[rt&lt;&lt;<span class="number">1</span>],treen[rt&lt;&lt;<span class="number">1</span>|<span class="number">1</span>]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">pushdown</span><span class="params">(<span class="type">int</span> rt)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(lazy[rt]==<span class="number">0</span>) <span class="keyword">return</span> ;</span><br><span class="line">    lazy[rt&lt;&lt;<span class="number">1</span>]+=lazy[rt];</span><br><span class="line">    lazy[rt&lt;&lt;<span class="number">1</span>|<span class="number">1</span>]+=lazy[rt];</span><br><span class="line">    treen[rt&lt;&lt;<span class="number">1</span>]-=lazy[rt];</span><br><span class="line">    treen[rt&lt;&lt;<span class="number">1</span>|<span class="number">1</span>]-=lazy[rt];</span><br><span class="line">    lazy[rt]=<span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">update</span><span class="params">(<span class="type">int</span> l,<span class="type">int</span> r,<span class="type">int</span> sl,<span class="type">int</span> sr,<span class="type">int</span> rt,<span class="type">int</span> val)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(l&gt;=sl &amp;&amp; r&lt;=sr) treen[rt]-=val,lazy[rt]+=val;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">pushdown</span>(rt);</span><br><span class="line">        <span class="type">int</span> mid=<span class="built_in">getMid</span>(l,r);</span><br><span class="line">        <span class="keyword">if</span>(mid&gt;=sl) <span class="built_in">update</span>(l,mid,sl,sr,rt&lt;&lt;<span class="number">1</span>,val);</span><br><span class="line">        <span class="keyword">if</span>(mid&lt;sr) <span class="built_in">update</span>(mid+<span class="number">1</span>,r,sl,sr,rt&lt;&lt;<span class="number">1</span>|<span class="number">1</span>,val);</span><br><span class="line">        treen[rt]=std::<span class="built_in">min</span>(treen[rt&lt;&lt;<span class="number">1</span>],treen[rt&lt;&lt;<span class="number">1</span>|<span class="number">1</span>]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">query</span><span class="params">(<span class="type">int</span> l,<span class="type">int</span> r,<span class="type">int</span> sl,<span class="type">int</span> sr,<span class="type">int</span> rt)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(l&gt;=sl &amp;&amp; r&lt;=sr) <span class="keyword">return</span> treen[rt];</span><br><span class="line">    <span class="keyword">if</span>(l&gt;sr || r&lt;sl) <span class="keyword">return</span> BIG;</span><br><span class="line">    <span class="type">int</span> mid=<span class="built_in">getMid</span>(l,r);</span><br><span class="line">    <span class="type">int</span> re=BIG;</span><br><span class="line">    <span class="built_in">pushdown</span>(rt);</span><br><span class="line">    <span class="keyword">if</span>(mid&lt;sr) re=std::<span class="built_in">min</span>(<span class="built_in">query</span>(mid+<span class="number">1</span>,r,sl,sr,rt&lt;&lt;<span class="number">1</span>|<span class="number">1</span>),re);</span><br><span class="line">    <span class="keyword">if</span>(mid&gt;=sl) re=std::<span class="built_in">min</span>(<span class="built_in">query</span>(l,mid,sl,sr,rt&lt;&lt;<span class="number">1</span>),re);</span><br><span class="line">    <span class="keyword">return</span> re;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    std::cin &gt;&gt; n &gt;&gt; m;</span><br><span class="line"></span><br><span class="line">    <span class="type">int</span> sn=n<span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;sn; i++) std::cin &gt;&gt; val[i];</span><br><span class="line">    <span class="built_in">build</span>(<span class="number">0</span>,n<span class="number">-2</span>,<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;m; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        std::cin &gt;&gt; p[i].first &gt;&gt; p[i].second;</span><br><span class="line">        <span class="keyword">if</span>(p[i].first &gt; p[i].second) std::<span class="built_in">swap</span>(p[i].first,p[i].second);</span><br><span class="line">        p[i].second-=<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    std::<span class="built_in">sort</span>(p,p+m,cmp);</span><br><span class="line">    ans=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;m; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="type">int</span> tt=<span class="built_in">query</span>(<span class="number">0</span>,n<span class="number">-2</span>,p[i].first,p[i].second,<span class="number">1</span>);</span><br><span class="line">        ans+=tt;</span><br><span class="line">        <span class="built_in">update</span>(<span class="number">0</span>,n<span class="number">-2</span>,p[i].first,p[i].second,<span class="number">1</span>,tt);</span><br><span class="line">    &#125;</span><br><span class="line">    std::cout &lt;&lt; ans;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E7%BA%BF%E6%AE%B5%E6%A0%91%20~%E4%B9%B1%20------------------------%E9%98%BF%E5%B7%B4%E9%98%BF%E5%B7%B4%E9%98%BF%E5%B7%B4/" data-id="cl2uhoedn005se4j39ico6mzz" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%BA%BF%E6%AE%B5%E6%A0%91/" rel="tag">线段树</a></li></ul>

    </footer>
  </div>
  
</article>




  


  <nav id="page-nav">
    <a class="extend prev" rel="prev" href="/page/6/">&lt;&lt;&lt; 上一页</a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/5/">5</a><a class="page-number" href="/page/6/">6</a><span class="page-number current">7</span><a class="page-number" href="/page/8/">8</a><a class="extend next" rel="next" href="/page/8/">下一页 &gt;&gt;&gt;</a>
  </nav>
</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>